00100	                     COMPUTER SCIENCE DEPARTMENT
00200	                         STANFORD UNIVERSITY
00300	
00400	
00500	CS 206           COMPUTING WITH SYMBOLIC EXPRESSIONS        FALL 1971
00600	
00700	
00800	                          FINAL EXAMINATION
00900	                         open book and notes
01000	
01005	
01010		1. Let the complex number  x+iy  be represented as an S-expression
01015	by the pair  (x . y); thus  3+4i  is represented as  (3 . 4).  Write an
01020	evaluator  ceval[e]  where  e  is an algebraic expression in  PLUS, TIMES,
01025	and complex and real constants.
01030	
01035		For example, we have
01040		
01045		ceval[(PLUS (3 . 4) 7 (TIMES (1 . 2) (2 . 1)))] = (10 . 9).
01047	
01050	
01100		2. conn[g] is true if and only if the directed graph g represented
01200	as described in chapter 1 of the class notes is connected in the sense
01300	that every vertex is reachable from every other vertex.  Write a LISP
01400	function for conn.
01500	
01600	
01700		3. Let u and v be  two  S-expressions.   Certain  of  the  atoms
01800	occurring  in  these  expressions  are regarded as variables, and the
01900	propositional expression isvar[x] will be true if x is a variable.  u
02000	and v may be assumed to have no variables in common.
02100	
02200		If there are substitutions for the variables in u and v  that
02300	make u and v the same expression, then match [u,v] is a list of pairs
02400	such that
02500	
02600		e =sublis[match[u,v],u] = sublis[match[u,v],v] for the most
02700	
02800	general e.  Otherwise, match[u,v] = NO.
02900	
03000		For example,
03100	
03200		match[(PLUS(TIMES X Y) Z), (PLUS ∪ (PLUS W Z))]   =
03300		((U . TIMES X Y)) (Z . PLUS W Z)))
03400	
03500	where the single letters are regarded as variables.
03600	
05400	
05500		4. Write a function to convert a list  of  English  words  to
05600	"Pig Latin."
05700	
05800	Each English word is translated to pig latin by the following rules:
05900	
06000	1.  if  the  first letter of the English word is a vowel then the pig
06100	latin translation is the same as the English word.
06200	
06300	2. Otherwise, rotate the first letter of the word to the end  of  the
06400	word  and  repeat  until the first letter becomes a vowel.    Add the
06500	letters "AY" to the end of the word you have and that is the answer.
06600	
06700	3.  For the puposes of this problem, vowels are A E I O and U.
06800	
06900	4.  Assume every English word contains at least one vowel.
07000	
07100	
07200	example:
07300	PIGLATIN('(I LIKE LISP BETTER THAN PIG LATIN)) =
07400		(I IKELAY ISPLAY ETTERBAY ANTHAY IGPAY ATINLAY)
07500	
07600	there are two functions in LISP that you will need:
07700	
07800		EXPLODE('APPLE) = '(A P P L E)
07900	and
08000		READLIST('(A P P L E)) = 'APPLE
08100